#include "DoubleLinkList.h"
#include <stdio.h>
#include <stdlib.h>


DLNode* CreateNode(ElementType element)
{
    DLNode *newNode = (DLNode*)malloc(sizeof(DLNode));
    if(newNode == NULL)
        return NULL;
    newNode->data = element;
    newNode->next = NULL;
    newNode->prev = NULL;
    return newNode;
}

void InitDLlist(DLlist *l)
{
    l->head = l->tail = CreateNode(NULL);
    l->len = 0;
}

void InsertTail1(DLlist *l, ElementType element)
{
    DLNode *newNode = CreateNode(element);
    if(newNode == NULL)
        return; 
    l->tail->next = newNode;
    newNode->prev = l->tail;
    l->tail = newNode;
    l->len++;
}

void InsertHead(DLlist *l, ElementType element)
{
    if(l->len == 0)
    {
        InsertTail1(l,element);
    }
    else
    {
        DLNode *newNode = CreateNode(element);
        if(newNode == NULL)
            return;
        newNode->next = l->head->next;
        l->head->next->prev = newNode;
        l->head->next = newNode;
        newNode->prev = l->head;
        l->len++;
    }
    
}

void InsertByIndex1(DLlist *l, int index, ElementType element)
{
    if(index <= 0 || index > l->len)
    {
        printf("插入位置非法!\n");
        return;
    }
    DLNode *newNode = CreateNode(element);
    DLNode *TravelPoint = l->head;
    for(int i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    newNode->next = TravelPoint->next;
    TravelPoint->next->prev = newNode;
    TravelPoint->next = newNode;
    newNode->prev = TravelPoint;
    l->len++;
}

void RemoveByIndex(DLlist *l, int index,void(*clearPtr)(ElementType))
{
    if(index < 0 || index >= l->len)
    {
        printf("删除非法位置!\n");
        return;
    }
    if(index == l->len - 1)
    {
        DLNode *Prev = l->tail->prev;
        Prev->next = NULL;
        if(clearPtr != NULL)
        {
            free(l->tail->data);
        }
        free(l->tail);
        l->tail = Prev;
        l->len--;
    }
    else
    {
        DLNode *TravelPoint = l->head;
        for(int i = 0; i < index; i++)
        {
            TravelPoint = TravelPoint->next;
        }
        DLNode *freeNode = TravelPoint->next;
        TravelPoint->next = freeNode->next;
        freeNode->next->prev = TravelPoint;
        if(clearPtr != NULL)
        {
            free(freeNode->data);
        }
        free(freeNode);
        l->len--;
    }
}

void RemoveByElement(DLlist *l,ElementType element,bool(*operPtr)(ElementType,ElementType),void(*clearPtr)(ElementType))
{
    DLNode *TravelPoint = l->head;
    int index = 0;
    while(TravelPoint->next != NULL)
    {
        if(operPtr(TravelPoint->next->data,element) == true)
        {
            RemoveByIndex(l,index,NULL);
        }
        else
        {
            index++;
            TravelPoint = TravelPoint->next;
        }
    }
}

ElementType* FindByIndex(DLlist *l,int index)
{
    if(index < 0 || index >= l->len)
    {
        printf("寻找位置非法!\n");
        return NULL;
    }
    DLNode* TravelPoint = l->head;
    for(int i = 0; i < index; i++)
    {
        TravelPoint = TravelPoint->next;
    }
    return &TravelPoint->next->data;
}

DLlist FindByElement(DLlist *l,ElementType element,bool(*operPtr)(ElementType,ElementType))
{
    DLlist list;
    InitDLlist(&list);
    DLNode* TravelPoint = l->head;
    while(TravelPoint->next != NULL)
    {
        if(operPtr(TravelPoint->next->data,element) == true)
        {
            InsertTail1(&list,TravelPoint->next->data);
        }
        TravelPoint = TravelPoint->next;
    }
    return list;
}
void Swap(ElementType *value1,ElementType *value2)
{
    ElementType temp = *value1;
    *value1 = *value2;
    *value2 = temp;
}
void FastSort(DLNode *start,DLNode *end,bool(*funcPtr)(void *,void *))
{
    if(start == end)
        return;
    DLNode *p1 = start;
    DLNode *p2 = p1->next;
    while(p2 != NULL)
    {
        if(p2->data < start->data)
        {
            p1 = p1->next;
            Swap(&p1->data,&p2->data);
        }
        p2 = p2->next;
    }
    Swap(&start->data,&p1->data);
    FastSort(start,p1,NULL);
    FastSort(p1->next,p2,NULL);
}

void DLlistSort(DLlist *list, bool (*funcPtr)(ElementType, ElementType))
{
    FastSort(list->head,NULL,funcPtr);
}

void ClearDLlist(DLlist *l,void(*clearPtr)(ElementType))
{
    while(l->head != NULL)
    {
        DLNode *next = l->head->next;
        if(l->head->next != NULL && clearPtr != NULL)
        {
            free(l->head->data);
        }
        free(l->head);
        l->head = next;
    }
}

void Travel(DLlist *l,void(*funcPtr)(ElementType))
{
    DLNode *TravelPoint = l->head;
    while(TravelPoint->next != NULL)
    {
        funcPtr(TravelPoint->next->data);
        TravelPoint = TravelPoint->next;
    }
    printf("\n");
}